
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

/*
There are two `sorted` arrays nums1 and nums2 of size m and n `respectively`.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

*/
class Solution {
public:	
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int N1 = nums1.size();
		int N2 = nums2.size();
		if (N1 < N2) return findMedianSortedArrays(nums2, nums1);	// Make sure A2 is the shorter one.

		int lo = 0, hi = N2 * 2;
		while (lo <= hi) {
			int mid2 = (lo + hi) / 2;   // Try Cut 2 
			int mid1 = N1 + N2 - mid2;  // Calculate Cut 1 accordingly

			double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1 - 1) / 2];	// Get L1, R1, L2, R2 respectively
			double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2 - 1) / 2];
			double R1 = (mid1 == N1 * 2) ? INT_MAX : nums1[(mid1) / 2];
			double R2 = (mid2 == N2 * 2) ? INT_MAX : nums2[(mid2) / 2];

			if (L1 > R2) lo = mid2 + 1;		// A1's lower half is too big; need to move C1 left (C2 right)
			else if (L2 > R1) hi = mid2 - 1;	// A2's lower half too big; need to move C2 left.
			else return (max(L1, L2) + min(R1, R2)) / 2;	// Otherwise, that's the right cut.
		}
		return -1;
	}
	
	double findMedianSortedArrays_0(vector<int>& nums1, vector<int>& nums2) {
		double median = 0;
		
		multiset<int> numSet;
		
		for (auto num : nums1)
		{
			numSet.insert(num);
		}

		for (auto num : nums2)
		{
			numSet.insert(num);
		}

		cout <<"set:"<<endl;
		for (auto num : numSet)
		{
			cout << num << " ";
		}
		cout << endl;

		int size = numSet.size();		
		auto itr = numSet.begin();
		int i = 0;
		while (i < size / 2)
		{
			++itr;
			++i;
		}
						
		if (size % 2 == 0)
		{
			median = *itr;
			--itr;			
			median = (median + *itr) / 2;
		}
		else
		{
			median = *itr;
		}
		
		return median;
	}
	/*
	wtanksleyjr  Report:
	Beautiful code.
	However, this is (m+n)*log(m+n) time and linear space; and the problem asked for log(m+n) time.
	You can do the same thing in constant space and linear time by pretending to merge the two arrays 
	without building any sets (just iterate through the two arrays from left to right, 
	and stop when you've processed all the elements before the index of the median). 
	This still doesn't solve the problem as stated (since linear is slower than log), 
	but it beats building a whole n*log(n) data structure.
	Oh, the multiset has n inserts, each of which is log(n) time. It therefore takes n*log(n) time to build.
	*/
	double findMedianSortedArrays_1(vector<int>& nums1, vector<int>& nums2) 
	{
		vector<int> nums;
		int i = 0;
		int j = 0;
		int len1 = nums1.size();
		int len2 = nums2.size();
		int pos =(len1 + len2) / 2;
		nums.reserve(pos + 1); //pre alloc memory
		
		for (; i < len1 && j < len2;)
		{
			if (nums1[i] < nums2[j])
			{
				nums.push_back(nums1[i]);
				i++;
			}
			else if (nums1[i] == nums2[j])
			{
				nums.push_back(nums1[i]);
				nums.push_back(nums2[j]);
				i++;
				j++;
			}
			else
			{
				nums.push_back(nums2[j]);				
				j++;
			}

			if (nums.size() > pos) //stop after find midian
			{
				break;
			}
		}

		if (nums.size() <= pos)
		{
			if (i<len1)
			{
				/*for (auto num:nums1)
					nums.push_back(num);*/
				for (; i < len1; i++)
				{
					nums.push_back(nums1[i]);
					if (nums.size() > pos) //stop after find midian
					{
						break;
					}
				}
					
			}
			if (j<len2)
			{				
				for (; j < len2; j++)
				{
					nums.push_back(nums2[j]);
					if (nums.size() > pos) //stop after find midian
					{
						break;
					}
				}					
			}
		}

		double median = 0;
		if ((len1 + len2) % 2 == 0)
		{
			median = (double)(nums[pos-1]+ nums[pos]) / 2;
		}
		else
		{
			median = nums[pos];
		}

		return median;
	}	

	int getkth(int s[], int m, int l[], int n, int k) {
		// let m <= n
		if (m > n)
			return getkth(l, n, s, m, k);
		if (m == 0)
			return l[k - 1];
		if (k == 1)
			return min(s[0], l[0]);

		int i = min(m, k / 2), j = min(n, k / 2);
		if (s[i - 1] > l[j - 1])
			return getkth(s, m, l + j, n - j, k - j);
		else
			return getkth(s + i, m - i, l, n, k - i);
		return 0;
	}

	//Binary search.Call 2 times getkth and k is about half of(m + n).Every time call getkth can reduce the scale k to its half.So the time complexity is log(m + n).
	double findMedianSortedArrays_2(int A[], int m, int B[], int n) {
		int l = (m + n + 1) >> 1;
		int r = (m + n + 2) >> 1;
		return (getkth(A, m, B, n, l) + getkth(A, m, B, n, r)) / 2.0;
	}
};

int _findMedianSortedArrays()
{
	Solution solu;
	double median = 0;
	vector<int> nums1 = {};// {1, 2};// { 1, 3 }; //{ 1,1 };// 
	vector<int> nums2 = {1};// { 3, 4 };// { 2 };//{ 1,2 };// 

	cout << "nums1:" << endl;
	for (auto num : nums1) cout << num << " ";
	cout << endl;
	cout << "nums2:" << endl;
	for (auto num : nums2) cout << num << " ";
	cout << endl;
	median = solu.findMedianSortedArrays(nums1, nums2);

	cout << "median:" << median << endl;

	return 0;
}